package leetcode_901_1000;

import java.util.Arrays;
import java.util.Random;

public class LeeCode_912 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(sortArray(new int[]{3, 2, 1, 5, 4})));
//        System.out.println(Arrays.toString(sortArray(new int[]{5,1,1,2,0,0})));
//        System.out.println(Arrays.toString(sortArray(new int[]{-4,0,7,4,9,-5,-1,0,-7,-1})));
        System.out.println(Arrays.toString(sortArray(new int[]{-4, 0, 0, 7, 7, -1})));
//        int[] arr = new int[100];
//        for (int i = 100, j = 0; i > 0; i--, j++) {
//            arr[j] = i;
//        }
//        System.out.println(Arrays.toString(sortArray(arr)));
//        System.out.println(Arrays.toString(sortArray(new int[]{5, 2, 3, 1})));
    }
    private static int[] sortArray(int[] nums) {
        if (special(nums)){
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    private static void quickSort(int[] nums, int l, int r){
        if (l >= r)
            return;
        Random random = new Random();
        int bi = random.nextInt(r - l + 1) + l;
        System.out.println(bi);
        int base = nums[bi], start = l, end = r;
        while (l < r){
            if (l == bi){
                l++;
            }
            if (r == bi){
                r--;
            }
            while (l < r && nums[r] >= base){
                r--;
                if (r == bi)
                    r--;
            }
            while (l < r && nums[l] <= base){
                l++;
                if (l == bi)
                    l++;
            }
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
        }

        quickSort(nums, start, l - 1);
        quickSort(nums, l + 1, end);
    }
    private static boolean special(int[] arr){
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i : arr) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        return max == min;
    }
}
